package com.cdream.basic.algorithm.leetcode.tree;

import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @author cdream
 * @date 2022/3/23
 */
public class Question440 {
    public static void main(String[] args) {
        new Question440().findKthNumber(681692778,351251360);
    }
    public int findKthNumber(int n, int k) {
        int p = 1;
        int prefix = 1;
        while(p<k){
            int cnt = getCount(prefix,n);
            if(cnt + p>k){
                prefix *= 10;
                p++;
            }else {
                prefix += 1;
                p += cnt;
            }
        }
        return prefix;

    }
    int getCount(int prefix,long max){
        int cnt = 0;
        long cur = prefix;
        long next = prefix + 1;
        while(cur<=max){
            cnt += Math.min(next, max+1) - cur;
            cur *= 10;
            next *= 10;
        }
        return cnt;
    }

    public String mostCommonWord(String paragraph, String[] banned) {
        Map<String, List<String>> map = Arrays.stream(banned).filter(a -> !paragraph.equalsIgnoreCase(a)).map(String::toLowerCase).collect(Collectors.groupingBy(a -> a));
        int cnt = 0;
        String res = "";
        for (Map.Entry<String, List<String>> entry : map.entrySet()) {
            String k = entry.getKey();
            List<String> v = entry.getValue();
            if (v.size()>cnt){
                cnt = v.size();
                res = k;
            }
        }
        return res;
    }
}
